Stone Game IV

记忆化搜索，这里稍微用了一下状态压缩On&On

#define MAX 30000
#define get(x) ((a[x/4] >> ((x%4)<<1)) & 3)
#define set(x,y) a[x/4] = a[x/4] & ~(3<<((x%4)<<1)) | (y << ((x%4)<<1)) 

class Solution {
public:
    char a[MAX];
    bool winnerSquareGame(int n) {
        memset(a, 0, sizeof(char)*MAX);
        return find(n);
    }

    bool find(int x) {
        if (x<MAX && get(x) != 0) {
            return get(x) == 1;
        }
        int y = sqrt(x);
        if (x == y*y) {
            set(x, 1);
            return true;
        }
        while(y > 0 && find(x-y*y)) {
            y--;
        }
        if (y != 0) {
            set(x, 1);
        } else {
            set(x, 2);
        }
        return y != 0;
    }
};